package com.awei.study.dataStructure.arr;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class arr_demo {


    /**
     * 合并数组
     */
    @Test
    public void mergeArr() {
        int a[] = new int[]{1, 3, 5, 2, 4, 6};
        int b[] = new int[a.length];
        int c[] = new int[a.length];
        mergeBfs(a, 0, 2, 3, 5, b, 0);
        System.out.println(Arrays.toString(b));
        merge(a, 0, 2, 3, 5, c);
        System.out.println(Arrays.toString(c));
    }

    /**
     * 非递归
     *
     * @param a 123
     * @param i
     * @param iEnd
     * @param j
     * @param jEnd
     * @param c
     */
    public void merge(int[] a, int i, int iEnd, int j, int jEnd, int[] c) {
        int k = 0;
        while (i <= iEnd && j <= jEnd) {
            if (a[i] < a[j]) {
                c[k] = a[i];
                i++;
            } else {
                c[k] = a[j];
                j++;
            }
            k++;
        }

//        System.out.println(Arrays.toString(c));

        if (i > iEnd) {
            System.arraycopy(a, j, c, k, jEnd - j + 1);
        }

        if (j > jEnd) {
            System.arraycopy(a, i, c, k, iEnd - i + 1);
        }
    }

    /**
     * 递归
     *
     * @param a
     * @param i
     * @param iEnd
     * @param j
     * @param jEnd
     * @param b
     * @param k
     */
    public void mergeBfs(int a[], int i, int iEnd, int j, int jEnd, int b[], int k) {
        if (i > iEnd) {
            System.arraycopy(a, j, b, k, jEnd - j + 1);
            return;
        }

        if (j > jEnd) {
            System.arraycopy(a, i, b, k, iEnd - i + 1);
            return;
        }
        if (a[i] < a[j]) {
            b[k] = a[i];
            mergeBfs(a, i + 1, iEnd, j, jEnd, b, k + 1);
        } else {
            b[k] = a[j];
            mergeBfs(a, i, iEnd, j + 1, jEnd, b, k + 1);
        }
    }

}
